---
id: 复杂度
title: 衡量算法好坏的标准
---

## 时间复杂度

由于受语言，运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。
但我们却可以预估代码的基本操作执行次数(计算量)，来做为时间复杂度，执行次数越多，则时间复杂度也就越高。

### 案例：时间复杂度 O(1)

```js
// 变量的取值赋值

let obj = { value: "xxx" };
obj.value; // O(1)
obj.value = 222; // O(1)

let arr = [1, 3, 4];
arr[1]; // O(1)
arr[2] = 4; // O(1)
```

### 案例：时间复杂度 O(n)

```js
function sum(num) {
  // 1
  let s = 0;
  // n
  for (let n = 0; n <= num; n++) {
    s += n;
  }
  return s;
}

console.log(sum(100));
```

:::tip 分析
sum 方法的时间复杂度用函数表示: T(n) = 1+n  
其中 n 是主导部分 可写成 T(n)  
大 O 表示法可写成 O(n)
:::

### 案例：时间复杂度 O(n)平方

```js
let 执行次数 = 0;

function sum(num) {
  let s = 0;
  for (let n = 0; n < num; n++) {
    for (let k = 1; k <= num; k++) {
      执行次数 += 1;
      s += k;
    }
  }
  return s;
}

console.log(sum(4)); // 40 
console.log("执行次数：", 执行次数); // 16
```

:::tip 分析
sum 方法的时间复杂度用函数表示: T(n) = 1+n²  
其中 n² 是主导部分 可写成 T(n²)  
大 O 表示法可写成 O(n²)
:::

### 案例：时间复杂度 O(logn)

```js
let 执行次数 = 0;

let n = 16;
for (let k = n; k > 1; k /= 2) {
  执行次数 += 1;
}
console.log("执行次数：", 执行次数);
```

:::tip 分析结果
O(logn)
:::

<!-- 我有一个好朋友叫张三。

他家里有 2 只狗，每天需要遛，且每次只能遛一条，每条遛 20 分钟。

2\*20=40 分钟，可以用函数表示 T(n) = 20n。

在这里计算量是 2 次，

张三很喜欢狗，找了一家宠物店的工作，负责 32 条狗的洗澡任务。
第一条洗澡用了 1 分钟，越洗越累。第二条用了 2 分钟，后面的每一条也都是累加 1 分钟。

这不是小学时学的 1+2+3+…… 加到 100 等于多少的问题。
根据高斯算法，此时吃掉整个面包需要 1+2+3+...+(n-1)+ n 即(1+n)×n/2 分钟，
也就是 0.5n^2 + 0.5n 分钟，记作 T(n) = 0.5n^2 + 0.5n。

张三每 10 分钟，可以洗一半的狗，既 10 分钟剩 16 条，20 分钟还剩 8 条，30 分钟还剩下 4 条……，
洗的只剩下 1 条需要多少时间
数字 32 不断地除以 2，涉及数学中的对数。(省略底数 2)
10 \* log32 = 50 分钟。
用函数表示就是 T(n) = 10logn。 -->

## 渐进时间复杂度(大O表示法)

算法A的执行次数是T(n)= 100n，算法B的执行次数是T(n)= 5n2，这两个 到底谁的运行时间更长一些呢?这就要看n的取值了。

因此，为了解决时间分析的难题，有了渐进时间复杂度(asymptotic time complexity)的概念，其官方定义如下。

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的 常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算 法的渐进时间复杂度，简称为时间复杂度。

因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

## 空间复杂度

简单来说：时间复杂度是执行算法的时间成本，空间复杂度是执行算法的空间成本。

## 其它复杂度表示法

### 大 O 表示法

- 表示了所有上限中最小的那个上限。

### 大 𝛀 表示法

- 表示了所有下限中最大的那个下限。

### 大 𝚹 表示法

- 如果上限相同，那么就可以用大 𝚹 表示法。

## 练练手 - 复杂度分析

- 案例 1

```js
a = 5;
b = 6;
c = 10;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    x = i * i;
    y = j * j;
    z = i * j;
  }
}

for (let k = 0; k < n; k++) {
  w = a * k + 45;
  v = b * b;
}

d = 33;
```

:::tip 分析结果
函数表示：T(n) = 3+3n²+2n+1 = 3n²+2n+4 = T(n²) = O(n²)
:::

<!-- - 案例 2
- 案例 3
- 案例 4
- 案例 5
- 案例 6
- 案例 7
- 案例 8 -->
